#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <chrono>
#include <random>
#include <execution>

void demonstrate_parallel_algorithms() {
  std::cout << "  C++17 并行算法演示:\n\n";

  // 创建测试数据
  const size_t size = 1000000;
  std::vector<int> data(size);
  
  // 填充随机数据
  std::random_device rd;
  std::mt19937 gen(rd());
  std::uniform_int_distribution<> dis(1, 1000);
  
  std::generate(data.begin(), data.end(), [&]() { return dis(gen); });

  std::cout << "  数据大小: " << size << " 个元素\n\n";

  // 1. 排序算法
  std::cout << "  1. 排序算法 (std::sort):\n";

  auto data_seq = data;
  auto data_par = data;
  auto data_par_unseq = data;

  auto start = std::chrono::high_resolution_clock::now();
  std::sort(std::execution::seq, data_seq.begin(), data_seq.end());
  auto end = std::chrono::high_resolution_clock::now();
  auto seq_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

  start = std::chrono::high_resolution_clock::now();
  std::sort(std::execution::par, data_par.begin(), data_par.end());
  end = std::chrono::high_resolution_clock::now();
  auto par_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

  std::cout << "    顺序执行: " << seq_time.count() << " ms\n";
  std::cout << "    并行执行: " << par_time.count() << " ms\n";
  std::cout << "    加速比: " << static_cast<double>(seq_time.count()) / par_time.count() << "x\n";

  // 2. 查找算法
  std::cout << "\n  2. 查找算法 (std::find):\n";

  int target = data[size / 2];

  start = std::chrono::high_resolution_clock::now();
  auto it_seq = std::find(std::execution::seq, data.begin(), data.end(), target);
  end = std::chrono::high_resolution_clock::now();
  seq_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

  start = std::chrono::high_resolution_clock::now();
  auto it_par = std::find(std::execution::par, data.begin(), data.end(), target);
  end = std::chrono::high_resolution_clock::now();
  par_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

  std::cout << "    查找目标: " << target << "\n";
  std::cout << "    顺序执行: " << seq_time.count() << " ms\n";
  std::cout << "    并行执行: " << par_time.count() << " ms\n";

  // 3. 变换算法
  std::cout << "\n  3. 变换算法 (std::transform):\n";

  std::vector<int> result_seq(size);
  std::vector<int> result_par(size);

  start = std::chrono::high_resolution_clock::now();
  std::transform(std::execution::seq, data.begin(), data.end(), result_seq.begin(),
                 [](int x) { return x * x; });
  end = std::chrono::high_resolution_clock::now();
  seq_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

  start = std::chrono::high_resolution_clock::now();
  std::transform(std::execution::par, data.begin(), data.end(), result_par.begin(),
                 [](int x) { return x * x; });
  end = std::chrono::high_resolution_clock::now();
  par_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

  std::cout << "    顺序执行: " << seq_time.count() << " ms\n";
  std::cout << "    并行执行: " << par_time.count() << " ms\n";

  // 4. 归约算法
  std::cout << "\n  4. 归约算法 (std::reduce):\n";

  start = std::chrono::high_resolution_clock::now();
  int sum_seq = std::reduce(std::execution::seq, data.begin(), data.end());
  end = std::chrono::high_resolution_clock::now();
  seq_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

  start = std::chrono::high_resolution_clock::now();
  int sum_par = std::reduce(std::execution::par, data.begin(), data.end());
  end = std::chrono::high_resolution_clock::now();
  par_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

  std::cout << "    和: " << sum_seq << "\n";
  std::cout << "    顺序执行: " << seq_time.count() << " ms\n";
  std::cout << "    并行执行: " << par_time.count() << " ms\n";

  // 5. 计数算法
  std::cout << "\n  5. 计数算法 (std::count_if):\n";

  start = std::chrono::high_resolution_clock::now();
  auto count_seq = std::count_if(std::execution::seq, data.begin(), data.end(),
                                  [](int x) { return x > 500; });
  end = std::chrono::high_resolution_clock::now();
  seq_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

  start = std::chrono::high_resolution_clock::now();
  auto count_par = std::count_if(std::execution::par, data.begin(), data.end(),
                                  [](int x) { return x > 500; });
  end = std::chrono::high_resolution_clock::now();
  par_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

  std::cout << "    大于500的元素数: " << count_seq << "\n";
  std::cout << "    顺序执行: " << seq_time.count() << " ms\n";
  std::cout << "    并行执行: " << par_time.count() << " ms\n";

  // 6. 执行策略说明
  std::cout << "\n  6. 执行策略:\n";
  std::cout << "    - seq: 顺序执行（默认）\n";
  std::cout << "    - par: 并行执行（多线程）\n";
  std::cout << "    - par_unseq: 并行+向量化执行\n";
  std::cout << "    - unseq: 向量化执行（单线程SIMD）\n";

  // 7. 注意事项
  std::cout << "\n  7. 使用注意事项:\n";
  std::cout << "    - 并行算法需要编译器支持\n";
  std::cout << "    - 可能需要链接TBB或其他并行库\n";
  std::cout << "    - 小数据集可能没有性能提升\n";
  std::cout << "    - 需要确保操作是无副作用的\n";
  std::cout << "    - 注意线程安全性\n";

  // 8. 优势说明
  std::cout << "\n  并行算法的优势:\n";
  std::cout << "  - 利用多核CPU提高性能\n";
  std::cout << "  - 统一的API，易于使用\n";
  std::cout << "  - 自动负载均衡\n";
  std::cout << "  - 类型安全，编译期检查\n";
}

